#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#define M 26

int scope_level;
int hash_table_cnt=0;

using namespace std;

class symbol
{
friend class hash_table;
	
public:
	string status;
	symbol(string n,string t,string v);
	~symbol();
	string name;
	string type;
	string value;
	void print();
	symbol* next;

	private:

};
symbol::symbol(string n,string t,string v)
{
	name=n;
	type=t;
	value=v;
	status="NIL";
	next=0;
}

symbol::~symbol()
{
	name="NIL";
	type="NIL";
	value="NIL";
	status="NIL";
	next=0;
}
void symbol::print()
{
	cout<<"name "<<name<<" type "<<type;
	if (value!="NIL")
		cout<<"value "<<value;
	cout<<endl;
}

class hash_table
{
public:
	hash_table();
	int hash_function(string key,int i);
	symbol* hash[M+1];
	int hash_insert(string n,string t,string v);
	int hash_search(string n);
	int hash_search_insert(string n,string t,string v);
	symbol* first;
	symbol* last;
	int cnt;
};

hash_table::hash_table()
{
	for (int i=0;i<M+1;i++)
	{
		hash[i]=new symbol("NIL","NIL","NIL");
		cnt=0;
		first=last=0;
	}
}

//hash_table::~hash_table()
//{
//	for (int i=0;i<M+2;i++)
//		hash[i]=0;
//}

int hash_table::hash_function(string key, int i)
{
	int key_length;
	int init_value;
	int map_value;

	key_length=key.length();
	init_value=key[0]-65;

	map_value=(init_value+key_length+i)%M;
	return map_value;
}

int hash_table::hash_insert(string n,string t,string v)
{
	int i;
	string key;
	int map_value;

	i=0;
	key=n;

	while(i!=M)	{
		map_value=hash_function(key,i);
//	cout<<"hash insert map value: "<<map_value<<" for name: "<<key<<endl;
//	cout<<"hash map value status: "<<hash[map_value]->status<<endl;
//	cout<<i<<endl;
		if (hash[map_value]->status=="NIL"||hash[map_value]->status=="DEL")
		{	
			hash[map_value]->name=n;
			hash[map_value]->type=t;
			hash[map_value]->value=v;
			hash[map_value]->status="FIL";
			if (cnt==0) {first=last=hash[map_value];}
			else
			{
				last->next=hash[map_value];
				last=hash[map_value];
			}
			cnt++;
			return map_value;
		}
		i++;
	}
	if (i==M)
	{
		cout<<"hash table overflower"<<endl;
		return -1;
	}
}

int hash_table::hash_search(string n)
{
	int i;
	int map_value;
	string key;

	key=n;
	i=0;

	while(i!=M) {
		map_value=hash_function(key,i);
//		cout<<"maped value in the hash table: "<<hash[map_value]->name<<endl<<"value search for: "<<key<<"status of value in hash table: "<<hash[map_value]->status<<endl;
		if ((hash[map_value]->name==key)&&(hash[map_value]->status=="FIL"))
		{
//			cout<<"key: "<<key<<" found in hash table: "<<"hash["<<map_value<<"] "<<hash[map_value]->name<<endl;
//			cout<<hash[map_value]->status<<endl;
			return map_value;
		}
		i++;
	}
	if (i==M)
	{
	//	cout<<"Symbol not found :"<<n<<endl;
	}
	return -1;
}

int hash_table::hash_search_insert(string n,string t,string v)
{
	int result;
	
	result=hash_search(n);
	if (result==-1)
	{
		result=hash_insert(n,t,v);
		return result;
	}
	else
	{
		cout<<"DECLARATION ERROR <"<<n<<">"<<endl;
		exit(EXIT_FAILURE);
	}
	return -1;
}

queue<string> stack_search(stack<hash_table> s,queue<string> sw,string n)
{
	int result;
	stack<hash_table> s_c;
	s_c=s;
	while (!s_c.empty())
	{
		result=s_c.top().hash_search(n);
		s_c.pop();
	}
	if (result!=-1)
	{
		sw.push(n);
	}
//	cout<<"stack search for "<<n<<" in scope "<<s.top().hash[M]->name<<" : "<<result<<endl;
	return sw;
}

/*
int main()
{
	int result;

	stack<hash_table> hash_stack;
	hash_table T1;
	hash_stack.push(T1);
	T1.hash_insert("a","int","NIL");
	result=T1.hash_search("a");
	hash_stack.top().hash[result]->print();
}

int main()
{	

	int result;
	hash_table T;
	result=T.hash_search("a");
	cout<<"result for search a: "<<result<<endl;
	result=T.hash_insert("a","int","0");
	cout<<"result for insert a first time: "<<result<<endl;
	if (result!=-1)
	{
		cout<<"symbol in hash table: "<<endl;
		T.hash[result]->print();
	}
	result=T.hash_insert("b","int","0");
	cout<<"result for insert b : "<<result<<endl;
	result=T.hash_search("a");
	cout<<"result for search 'a' second time "<<result<<endl;
	result=T.hash_insert("a","int","0");
	cout<<"result for insert 'a' second time "<<result<<endl;
	T.hash[result]->print();
	enter_new_scope();
	cout<<scope_level;
	leave_current_scope();
	cout<<scope_level;
}
*/
